package 常见算法.优先级队列堆;

import java.util.PriorityQueue;

/**
 * @Date 2024/6/18 22:13
 * @description: 第K 大元素 (用小跟堆)
 * .        https://leetcode.cn/problems/kth-largest-element-in-a-stream/
 * @Author LittleNight
 */
public class likou703 {

    // 利用 快速选择算法解决 TopK问题 https://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof/
    // 面试可能直接会说 用快速选择算法, 具体操作看上题
    // 此处我们用 堆 来解决

    // 1. 创建一个堆 (保证堆的大小为 K 个). (第 K 大, 创建小根堆)
    PriorityQueue<Integer> heap;
    int K;
    // 这个是构造方法
    public likou703(int k, int[] nums) {
        // 初始化
        K = k;
        heap  = new PriorityQueue<>(); // 默认就是小根堆
        // 2. 循环添加元素, 判断堆大小是否超过K, 超过之后, 弹出堆顶元素
        for(int x : nums) {
            heap.offer(x);
            // 保证堆的大小为 K 个
            if(heap.size() > K) {
                heap.poll();
            }
        }
    }

    public int add(int val) {
        heap.offer(val);
        if(heap.size() > K) {
            heap.poll();
        }
        // 小根堆顶元素就是第 K 大元素, 要注意是 peek 不是 弹出poll
        // int ret = heap.poll();
        int ret = heap.peek();
        return ret;
    }
}
